Rajeev Motwani

According to our database1, Rajeev Motwani authored at least 205 papers between 1986 and 2018.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 2007, "For contributions to algorithms and complexity theory.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2018
Studying the Potential of Multi-Target Classification on Patient Screening Data to Predict Dropout Cases.
Proceedings of the 31st IEEE International Symposium on Computer-Based Medical Systems, 2018

2016
The Sliding-Window Computation Model and Results.
Proceedings of the Data Stream Management - Processing High-Speed Data Streams, 2016

STREAM: The Stanford Data Stream Management System.
Proceedings of the Data Stream Management - Processing High-Speed Data Streams, 2016

2012
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality.
Theory of Computing, 2012

Online Graph Edge-Coloring in the Random-Order Arrival Model.
Theory of Computing, 2012

Distributing Data for Secure Database Services.
Trans. Data Privacy, 2012

Approximate Frequency Counts over Data Streams.
PVLDB, 2012

2011
Distributing data for secure database services.
Proceedings of the 2011 International Workshop on Privacy and Anonymity in Information Society, 2011

2010
Finding large cycles in Hamiltonian graphs.
Discrete Applied Mathematics, 2010

A 1.43-Competitive Online Graph Edge Coloring Algorithm in the Random Order Arrival Model.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

2009
On the graph turnpike problem.
Inf. Process. Lett., 2009

Pricing strategies for viral marketing on Social Networks
CoRR, 2009

Pricing Strategies for Viral Marketing on Social Networks.
Proceedings of the Internet and Network Economics, 5th International Workshop, 2009

2008
A Survey of Query Auditing Techniques for Data Privacy.
Proceedings of the Privacy-Preserving Data Mining - Models and Algorithms, 2008

Anonymizing Unstructured Data
CoRR, 2008

Auditing SQL Queries.
Proceedings of the 24th International Conference on Data Engineering, 2008

Link Privacy in Social Networks.
Proceedings of the 24th International Conference on Data Engineering, 2008

Link privacy in social networks.
Proceedings of the 17th ACM Conference on Information and Knowledge Management, 2008

2007
The Sliding-Window Computation Model and Results.
Proceedings of the Data Streams - Models and Algorithms, 2007

Load Shedding in Data Stream Systems.
Proceedings of the Data Streams - Models and Algorithms, 2007

Asymptotic Polynomial-Time Approximation Schemes.
Proceedings of the Handbook of Approximation Algorithms and Metaheuristics., 2007

Querying priced information in databases: The conjunctive case.
ACM Trans. Algorithms, 2007

Lower Bounds on Locality Sensitive Hashing.
SIAM J. Discrete Math., 2007

The price of validity in dynamic networks.
J. Comput. Syst. Sci., 2007

Computing shortest paths with uncertainty.
J. Algorithms, 2007

Tracing the Path: New Model and Algorithms for Collaborative Filtering.
Proceedings of the 23rd International Conference on Data Engineering Workshops, 2007

Auditing a Batch of SQL Queries.
Proceedings of the 23rd International Conference on Data Engineering Workshops, 2007

Estimating Sum by Weighted Sampling.
Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

2006
The load rebalancing problem.
J. Algorithms, 2006

k-connected spanning subgraphs of low degree.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Finding large cycles in Hamiltonian graphs.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Channel assignment in wireless networks and classification of minimum graph homomorphism.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Query Optimization over Web Services.
Proceedings of the 32nd International Conference on Very Large Data Bases, 2006

Towards Robustness in Query Auditing.
Proceedings of the 32nd International Conference on Very Large Data Bases, 2006

Truthful auctions for pricing search keywords.
Proceedings of the Proceedings 7th ACM Conference on Electronic Commerce (EC-2006), 2006

Evolution of page popularity under random web graph models.
Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2006

Keyword Generation for Search Engine Advertising.
Proceedings of the Workshops Proceedings of the 6th IEEE International Conference on Data Mining (ICDM 2006), 2006

Lower bounds on locality sensitive hashing.
Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006

Estimating corpus size via queries.
Proceedings of the 2006 ACM CIKM International Conference on Information and Knowledge Management, 2006

Fractional Matching Via Balls-and-Bins.
Proceedings of the Approximation, 2006

Distinct Values Estimators for Power Law Distributions.
Proceedings of the Third Workshop on Analytic Algorithmics and Combinatorics, 2006

2005
Scale-free aggregation in sensor networks.
Theor. Comput. Sci., 2005

Lower bounds on Locality Sensitive Hashing
CoRR, 2005

Finding large cycles in Hamiltonian graphs.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

The Pipelined Set Cover Problem.
Proceedings of the Database Theory, 2005

Algorithms for the Database Layout Problem.
Proceedings of the Database Theory, 2005

Anonymizing Tables.
Proceedings of the Database Theory, 2005

Robust Identification of Fuzzy Duplicates.
Proceedings of the 21st International Conference on Data Engineering, 2005

Adaptive Caching for Continuous Queries.
Proceedings of the 21st International Conference on Data Engineering, 2005

Two Can Keep A Secret: A Distributed Architecture for Secure Database Services.
Proceedings of the CIDR 2005, 2005

2004
Operator scheduling in data stream systems.
VLDB J., 2004

Combining request scheduling with web caching.
Theor. Comput. Sci., 2004

Incremental Clustering and Dynamic Information Retrieval.
SIAM J. Comput., 2004

Introduction: Special Issue on Theoretical Advances in Data Clustering.
Machine Learning, 2004

Modeling correlations in web traces and implications for designing replacement policies.
Computer Networks, 2004

Combinatorial and Experimental Methods for Approximate Point Pattern Matching.
Algorithmica, 2004

Vision Paper: Enabling Privacy for the Paranoids.
Proceedings of the (e)Proceedings of the Thirtieth International Conference on Very Large Data Bases, Toronto, Canada, August 31, 2004

Caching queues in memory buffers.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

The Price of Validity in Dynamic Networks.
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2004

Adaptive Ordering of Pipelined Stream Filters.
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2004

Load Shedding for Aggregation Queries over Data Streams.
Proceedings of the 20th International Conference on Data Engineering, 2004

Algorithms for Multi-product Pricing.
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

On Identifying Stable Ways to Configure Systems.
Proceedings of the 1st International Conference on Autonomic Computing (ICAC 2004), 2004

Aggregating Correlated Data in Sensor Networks.
Proceedings of the Combinatorial and Algorithmic Aspects of Networking, 2004

Scale Free Aggregation in Sensor Networks.
Proceedings of the Algorithmic Aspects of Wireless Sensor Networks: First International Workshop, 2004

2003
Clustering Data Streams: Theory and Practice.
IEEE Trans. Knowl. Data Eng., 2003

List Partitions.
SIAM J. Discrete Math., 2003

Computing the Median with Uncertainty.
SIAM J. Comput., 2003

A combinatorial algorithm for MAX CSP.
Inf. Process. Lett., 2003

STREAM: The Stanford Stream Data Manager.
IEEE Data Eng. Bull., 2003

Computing Shortest Paths with Uncertainty.
Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

Representing Graph Metrics with Fewest Edges.
Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

The load rebalancing problem.
Proceedings of the SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2003

Robust and Efficient Fuzzy Match for Online Data Cleaning.
Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, 2003

Chain : Operator Scheduling for Memory Minimization in Data Stream Systems.
Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, 2003

Maintaining variance and k-medians over data stream windows.
Proceedings of the Twenty-Second ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2003

Challenges in Web Search Engines.
Proceedings of the IJCAI-03, 2003

Switch Scheduling via Randomized Edge Coloring.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

Query Processing, Approximation, and Resource Management in a Data Stream Management System.
Proceedings of the CIDR 2003, 2003

Introduction to automata theory, languages, and computation - international edition (2. ed).
Addison-Wesley, ISBN: 978-0-321-21029-6, 2003

2002
Challenges in web search engines.
SIGIR Forum, 2002

Approximating the Longest Cycle Problem in Sparse Graphs.
SIAM J. Comput., 2002

Maintaining Stream Statistics over Sliding Windows.
SIAM J. Comput., 2002

Worst-case time bounds for coloring and satisfiability problems.
J. Algorithms, 2002

Approximate Frequency Counts over Data Streams.
Proceedings of the VLDB 2002, 2002

Web caching with request reordering.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Maintaining stream statistics over sliding windows (extended abstract).
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Sampling from a moving window over streaming data.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Models and Issues in Data Stream Systems.
Proceedings of the Twenty-first ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2002

Streaming-Data Algorithms for High-Quality Clustering.
Proceedings of the 18th International Conference on Data Engineering, San Jose, CA, USA, February 26, 2002

Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie (2. Aufl.).
Pearson Studium, ISBN: 978-3-8273-7020-4, 2002

2001
Finding Interesting Associations without Support Pruning.
IEEE Trans. Knowl. Data Eng., 2001

Introduction to automata theory, languages, and computation, 2nd edition.
SIGACT News, 2001

Approximation Techniques for Average Completion Time Scheduling.
SIAM J. Comput., 2001

Guest Editor's Foreword.
J. Comput. Syst. Sci., 2001

Overcoming Limitations of Sampling for Aggregation Queries.
Proceedings of the 17th International Conference on Data Engineering, 2001

Optimizing iterative decoding of low-density parity check codes on programmable pipelined parallel architectures.
Proceedings of the Global Telecommunications Conference, 2001

Introduction to automata theory, languages, and computation - (2. ed.).
Addison-Wesley series in computer science, Addison-Wesley-Longman, ISBN: 978-0-201-44124-6, 2001

2000
Scalable Techniques for Mining Causal Structures.
Data Min. Knowl. Discov., 2000

Guest Editors' Foreword.
Algorithmica, 2000

On the decidability of accessibility problems (extended abstract).
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Finding long paths and cycles in sparse Hamiltonian graphs.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Computing the median with uncertainty.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Accurate approximations for Asian options.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Towards Estimation Error Guarantees for Distinct Values.
Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2000

Mining the stock market (extended abstract): which measure is best?
Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, 2000

Dynamic Miss-Counting Algorithms: Finding Implication and Similarity Rules with Confidence Pruning.
Proceedings of the 16th International Conference on Data Engineering, San Diego, California, USA, February 28, 2000

Finding Interesting Associations without Support Pruning.
Proceedings of the 16th International Conference on Data Engineering, San Diego, California, USA, February 28, 2000

Clustering Data Streams.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999
Approximating Capacitated Routing and Delivery Problems.
SIAM J. Comput., 1999

Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication).
SIAM J. Comput., 1999

The Angular-Metric Traveling Salesman Problem.
SIAM J. Comput., 1999

Path Planning in Expansive Configuration Spaces.
Int. J. Comput. Geometry Appl., 1999

A Visibility-Based Pursuit-Evasion Problem.
Int. J. Comput. Geometry Appl., 1999

Complexity Measures for Assembly Sequences.
Int. J. Comput. Geometry Appl., 1999

On Sampling and Relational Operators.
IEEE Data Eng. Bull., 1999

Precedence Constrained Scheduling to Minimize Sum of Weighted Completion Times on a Single Machine.
Discrete Applied Mathematics, 1999

Similarity Search in High Dimensions via Hashing.
Proceedings of the VLDB'99, 1999

Complexity of Graph Partition Problems.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Geometric Matching Under Noise: Combinatorial Bounds and Algorithms.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Minimizing Weighted Completion Time on a Single Machine.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

On Random Sampling over Joins.
Proceedings of the SIGMOD 1999, 1999

Geometric Pattern Matching: A Performance Study.
Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 1999

1998
On Syntactic versus Computational Views of Approximability.
SIAM J. Comput., 1998

Randomized Query Processing in Robot Path Planning.
J. Comput. Syst. Sci., 1998

Realization of Matrices and Directed Graphs.
J. Algorithms, 1998

Approximate Graph Coloring by Semidefinite Programming.
J. ACM, 1998

Proof Verification and the Hardness of Approximation Problems.
J. ACM, 1998

Online Scheduling with Lookahead: Multipass Assembly Lines.
INFORMS Journal on Computing, 1998

Proof verification and the hardness of approximation problems.
Electronic Colloquium on Computational Complexity (ECCC), 1998

What can you do with a Web in your Pocket?
IEEE Data Eng. Bull., 1998

Beyond Market Baskets: Generalizing Association Rules to Dependence Rules.
Data Min. Knowl. Discov., 1998

Approximate Graph Coloring by Semidefinite Programming
CoRR, 1998

RAPID: Randomized pharmacophore identification for drug design.
Comput. Geom., 1998

Approximating Probability Distributions Using Small Sample Spaces.
Combinatorica, 1998

On Certificates and Lookahead in Dynamic Graph Problems.
Algorithmica, 1998

Scalable Techniques for Mining Causal Structures.
Proceedings of the VLDB'98, 1998

Computing Iceberg Queries Efficiently.
Proceedings of the VLDB'98, 1998

Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

The Dynamic Servers Problem.
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

Query Flocks: A Generalization of Association-Rule Mining.
Proceedings of the SIGMOD 1998, 1998

Extracting Schema from Semistructured Data.
Proceedings of the SIGMOD 1998, 1998

Random Sampling for Histogram Construction: How much is enough?
Proceedings of the SIGMOD 1998, 1998

Capturing the Connectivity of High-Dimensional Geometric Spaces by Parallelizable Random Sampling Techniques.
IPPS/SPDP Workshops, 1998

1997
Infering Structure in Semistructured Data.
SIGMOD Record, 1997

An NC Algorithm for Minimum Cuts.
SIAM J. Comput., 1997

The Robot Localization Problem.
SIAM J. Comput., 1997

A Random Sampling Scheme for Path Planning.
I. J. Robotics Res., 1997

On Approximating the Longest Path in a Graph.
Algorithmica, 1997

Visibility-Based Pursuit-Evasion in a Polygonal Environment.
Proceedings of the Algorithms and Data Structures, 5th International Workshop, 1997

Intractability of Assembly Sequencing: Unit Disks in the Plane.
Proceedings of the Algorithms and Data Structures, 5th International Workshop, 1997

Constrained TSP and Low-Power Computing.
Proceedings of the Algorithms and Data Structures, 5th International Workshop, 1997

Locality-Preserving Hashing in Multidimensional Spaces.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Incremental Clustering and Dynamic Information Retrieval.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Approximation Techniques for Average Completion Time Scheduling.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

The Angular-Metric Traveling Salesman Problem.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Dynamic Itemset Counting and Implication Rules for Market Basket Data.
Proceedings of the SIGMOD 1997, 1997

Beyond Market Baskets: Generalizing Association Rules to Correlations.
Proceedings of the SIGMOD 1997, 1997

Finding an unpredictable target in a workspace with obstacles.
Proceedings of the 1997 IEEE International Conference on Robotics and Automation, 1997

Path planning in expansive configuration spaces.
Proceedings of the 1997 IEEE International Conference on Robotics and Automation, 1997

Nonholonomic path planning for pushing a disk among obstacles.
Proceedings of the 1997 IEEE International Conference on Robotics and Automation, 1997

Storage Management for Evolving Databases.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

RAPID: Randomized Pharmacophore Identification for Drug Design.
Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997

Randomized Algorithms.
Proceedings of the Computer Science and Engineering Handbook, 1997

1996
Randomized Algorithms.
ACM Comput. Surv., 1996

Geometric Manipulation of Flexible Ligands.
Proceedings of the Applied Computational Geormetry, 1996

Towards a Syntactic Characterization of PTAS.
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

On Certificates and Lookahead in Dynamic Graph Problems.
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

Fast Estimation of Diameter and Shortest Paths (without Matrix Multiplication).
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

Profile-driven Instruction Level Parallel Scheduling with Application to Super Blocks.
Proceedings of the 29th Annual IEEE/ACM International Symposium on Microarchitecture, 1996

Complexity measures for assembly sequences.
Proceedings of the 1996 IEEE International Conference on Robotics and Automation, 1996

1995
Randomized Algorithms.
SIGACT News, 1995

Tail Bounds for Occupancy and the Satisfiability Threshold Conjecture.
Random Struct. Algorithms, 1995

Clique Partitions, Graph Compression and Speeding-Up Algorithms.
J. Comput. Syst. Sci., 1995

On Syntactic versus Computational Views of Approximability
Electronic Colloquium on Computational Complexity (ECCC), 1995

Coloring Away Communication in Parallel Query Optimization.
Proceedings of the VLDB'95, 1995

Randomized query processing in robot path planning (Extended Abstract).
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Scheduling Problems in Parallel Query Optimization.
Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1995

Randomized Algorithms.
Cambridge University Press, ISBN: 0-521-47465-5, 1995

1994
Non-Clairvoyant Scheduling.
Theor. Comput. Sci., 1994

The Probabilistic Method Yields Deterministic Parallel Algorithms.
J. Comput. Syst. Sci., 1994

Average-Case Analysis of Algorithms for Matchings and Related Problems.
J. ACM, 1994

Computing Roots of Graphs Is Hard.
Discrete Applied Mathematics, 1994

Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism.
Proceedings of the VLDB'94, 1994

On Syntactic versus Computational Views of Approximability
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

Approximate Graph Coloring by Semidefinite Programming
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

Tail Bounds for Occupancy and the Satisfiability Threshold Conjecture
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993
Probabilistic Analysis of Network Flow Algorithms.
Math. Oper. Res., 1993

On Approximating the Longest Path in a Graph (Preliminary Version).
Proceedings of the Algorithms and Data Structures, Third Workshop, 1993

Non-Clairvoyant Scheduling.
Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

1992
A Linear Time Approach to the Set Maxima Problem.
SIAM J. Discrete Math., 1992

The Greedy Algorithm is Optimal for On-Line Edge Coloring.
Inf. Process. Lett., 1992

The Robot Localization Problem in Two Dimensions.
Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

Proof Verification and Hardness of Approximation Problems
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1991
Clique Partitions, Graph Compression, and Speeding-Up Algorithms
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

1990
Stable Husbands.
Random Struct. Algorithms, 1990

Covering Orthogonal Polygons with Star Polygons: The Perfect Graph Approach.
J. Comput. Syst. Sci., 1990

Stable Husbands.
Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990

1989
Perfect Graphs and Orthogonally Convex Covers.
SIAM J. Discrete Math., 1989

Expanding Graphs and the Average-case Analysis of Algorithms for Matchings and Related Problems
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

The Probabilistic Method Yields Deterministic Parallel Algorithms
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

1988
Deferred Data Structuring.
SIAM J. Comput., 1988

Constructive Results from Graph Minors: Linkless Embeddings
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

Covering Orthogonal Polygons with Star Polygons: The Perfect Graph Approach.
Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988

1986
Deferred Data Structuring: Query-Driven Preprocessing for Geometric Search Problems.
Proceedings of the Second Annual ACM SIGACT/SIGGRAPH Symposium on Computational Geometry, 1986


  Loading...