ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Substring selectivity estimation
Full text PdfPdf (1.20 MB)
Source Symposium on Principles of Database Systems archive
Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems table of contents
Philadelphia, Pennsylvania, United States
Pages: 249 - 260  
Year of Publication: 1999
ISBN:1-58113-062-7
Authors
H. V. Jagadish  U of Illinois, Urbana-Champaign
Raymond T. Ng  U of British Columbia
Divesh Srivastava  AT&T Labs-Research
Sponsors
SIGART: ACM Special Interest Group on Artificial Intelligence
SIGMOD: ACM Special Interest Group on Management of Data
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 3,   Downloads (12 Months): 19,   Citation Count: 15
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/303976.304001
What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

1
Mauricio A. Hernández , Salvatore J. Stolfo, The merge/purge problem for large databases, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.127-138, May 22-25, 1995, San Jose, California, United States
 
2
Tim Howes , Mark Smith, LDAP: programming directory-enabled applications with lightweight directory access protocol, Macmillan Publishing Co., Inc., Indianapolis, IN, 1997
 
3
Yannis E. Ioannidis, Universality of Serial Histograms, Proceedings of the 19th International Conference on Very Large Data Bases, p.256-267, August 24-27, 1993
4
Yannis E. Ioannidis , Viswanath Poosala, Balancing histogram optimality and practicality for query result size estimation, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.233-244, May 22-25, 1995, San Jose, California, United States
 
5
H. V. Jagadish , Nick Koudas , S. Muthukrishnan , Viswanath Poosala , Kenneth C. Sevcik , Torsten Suel, Optimal Histograms with Quality Guarantees, Proceedings of the 24rd International Conference on Very Large Data Bases, p.275-286, August 24-27, 1998
6
P. Krishnan , Jeffrey Scott Vitter , Bala Iyer, Estimating alphanumeric selectivity in the presence of wildcards, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.282-293, June 04-06, 1996, Montreal, Quebec, Canada
7
Richard J. Lipton , Jeffrey F. Naughton, Query size estimation by adaptive sampling (extended abstract), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.40-46, April 02-04, 1990, Nashville, Tennessee, United States  [doi>10.1145/298514.298540]
8
Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976  [doi>10.1145/321941.321946]
9
M. Muralikrishna , David J. DeWitt, Equi-depth multidimensional histograms, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.28-36, June 01-03, 1988, Chicago, Illinois, United States
10
Viswanath Poosala , Peter J. Haas , Yannis E. Ioannidis , Eugene J. Shekita, Improved histograms for selectivity estimation of range predicates, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.294-305, June 04-06, 1996, Montreal, Quebec, Canada
 
11
Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
12
P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts  [doi>10.1145/582095.582099]
 
13
C. E. Shannon. Prediction and entropy of printed english. Bell systems technica,! journal, 30(1):50-64, 1951.
 
14
Transaction Processing Performance Council (TPC), 777 N. First Street, Suite 600, San Jose, CA 95112, USA. TPC Benchmar,~ 13 (Decision Support), May 1995.
 
15
P. Weiner. Linear pattern matching algorithms. In Proceedings of the IEEE l~th Annual Symposium on Switching and Automata Theory, pages 1-11, 1973.

CITED BY  15
Zhiyuan Chen , Nick Koudas , Flip Korn , S. Muthukrishnan, Selectively estimation for Boolean queries, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.216-225, May 15-18, 2000, Dallas, Texas, United States
Dennis Shasha , Jason T. L. Wang , Rosalba Giugno, Algorithmics and applications of tree and graph searching, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
Zhiyuan Chen , Flip Korn , Nick Koudas , S. Muthukrishnan, Generalized substring selectivity estimation, Journal of Computer and System Sciences, v.66 n.1, p.98-132, 01 February 2003
Lipyeow Lim , Min Wang , Jeffrey Scott Vitter, CXHist: an on-line classification-based histogram for XML string selectivity estimation, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
Chen Li , Bin Wang , Xiaochun Yang, VGRAM: improving performance of approximate queries on string collections using variable-length grams, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
Arnab Nandi , H. V. Jagadish, Effective phrase prediction, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
Yannis Ioannidis, The history of histograms (abridged), Proceedings of the 29th international conference on Very large data bases, p.19-30, September 09-12, 2003, Berlin, Germany
Hongrae Lee , Raymond T. Ng , Kyuseok Shim, Extending q-grams to estimate selectivity of string matching with low edit distance, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
Lipyeow Lim , Min Wang , Sriram Padmanabhan , Jeffrey Scott Vitter , Ronald Parr, XPathLearner: an on-line self-tuning Markov histogram for XML path selectivity estimation, Proceedings of the 28th international conference on Very Large Data Bases, p.442-453, August 20-23, 2002, Hong Kong, China
H. V. Jagadish , Olga Kapitskaia , Raymond T. Ng , Divesh Srivastava, One-dimensional and multi-dimensional substring selectivity estimation, The VLDB Journal — The International Journal on Very Large Data Bases, v.9 n.3, p.214-230, December 2000
Ashraf Aboulnaga , Alaa R. Alameldeen , Jeffrey F. Naughton, Estimating the Selectivity of XML Path Expressions for Internet Scale Applications, Proceedings of the 27th International Conference on Very Large Data Bases, p.591-600, September 11-14, 2001
H. V. Jagadish , Olga Kapitskaia , Raymond T. Ng , Divesh Srivastava, Multi-Dimensional Substring Selectivity Estimation, Proceedings of the 25th International Conference on Very Large Data Bases, p.387-398, September 07-10, 1999
Xiaochun Yang , Bin Wang , Chen Li, Cost-based variable-length-gram selection for string collections to support approximate queries efficiently, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada
Stefano Lonardi , Jessica Lin , Eamonn Keogh , Bill Chiu, Efficient discovery of unusual patterns in time series, New Generation Computing, v.25 n.1, p.61-93, January 2007
Hongrae Lee , Raymond T. Ng , Kyuseok Shim, Approximate substring selectivity estimation, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS


General Terms:
Algorithms, Design, Experimentation, Management, Measurement, Performance, Theory

Collaborative Colleagues:
H. V. Jagadish: colleagues
Raymond T. Ng: colleagues
Divesh Srivastava: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player