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
Incremental clustering and dynamic information retrieval
Full text PdfPdf (1.58 MB)
Source Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-ninth annual ACM symposium on Theory of computing table of contents
El Paso, Texas, United States
Pages: 626 - 635  
Year of Publication: 1997
ISBN:0-89791-888-6
Authors
Moses Charikar  Department of Computer Science, Stanford University, Stanford, CA
Chandra Chekuri  Department of Computer Science, Stanford University, Stanford, CA
Tomás Feder  Department of Computer Science, Stanford University, Stanford, CA
Rajeev Motwani  Department of Computer Science, Stanford University, Stanford, CA
Sponsor
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 21,   Downloads (12 Months): 165,   Citation Count: 56
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/258533.258657
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
M.S. Aldenderfer and R.K. Blashfield. Cluster Analysis. Sage, Beverly Hills, 1984.
 
2
Marshall Bern , David Eppstein, Approximation algorithms for geometric problems, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
 
3
P. Brucker. On the complexity of clustering problems. In: R. Henn, B. Korte, and W. Oletti, editors, Optimization and Operations Research, Heidelberg, New York, NY, 1977, pp. 45-54.
4
Fazli Can, Incremental clustering for dynamic information processing, ACM Transactions on Information Systems (TOIS), v.11 n.2, p.143-164, April 1993  [doi>10.1145/130226.134466]
5
F. Can , E. Ozkarahan, A dynamic cluster maintenance system for information retrieval, Proceedings of the 10th annual international ACM SIGIR conference on Research and development in information retrieval, p.123-131, June 03-05, 1987, New Orleans, Louisiana, United States  [doi>10.1145/42005.42019]
 
6
E Can and N.D. Drochak II. Incremental Clustering for Dynamic Document Databases. In Proceedings of the 1990 Symposium on Applied Computing, 1990, pp. 61-67.
 
7
Soumen Chakrabarti , Cynthia A. Phillips , Andreas S. Schulz , David B. Shmoys , Clifford Stein , Joel Wein, Improved Scheduling Algorithms for Minsum Criteria, Proceedings of the 23rd International Colloquium on Automata, Languages and Programming, p.646-657, July 08-12, 1996
 
8
B. B. Chaudhuri, Dynamic clustering for time incremental data, Pattern Recognition Letters, v.15 n.1, p.27-34, Jan. 1994  [doi>10.1016/0167-8655(94)90097-3]
9
Douglass R. Cutting , David R. Karger , Jan O. Pedersen , John W. Tukey, Scatter/Gather: a cluster-based approach to browsing large document collections, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.318-329, June 21-24, 1992, Copenhagen, Denmark  [doi>10.1145/133160.133214]
10
Douglass R. Cutting , David R. Karger , Jan O. Pedersen, Constant interaction-time scatter/gather browsing of very large document collections, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.126-134, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States  [doi>10.1145/160688.160706]
 
11
Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
 
12
B. Everitt. Cluster Analysis. Heinemann Educational, London, 1974.
 
13
Christos Faloutsos , Douglas W. Oard, A survey of information retrieval and filtering methods, University of Maryland at College Park, College Park, MD, 1995
14
Tomás Feder , Daniel Greene, Optimal algorithms for approximate clustering, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.434-444, May 02-04, 1988, Chicago, Illinois, United States  [doi>10.1145/62212.62255]
 
15
R.J. Fowler, M.S. Paterson, and S.L. Tanimoto. Optimal packing and covering in the plane are NP-complete. Information Processing Letters, 12 (1981), pp. 133-137.
 
16
William B. Frakes , Ricardo Baeza-Yates, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
 
17
Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
 
18
Michel Goemans , Jon Kleinberg, An improved approximation ratio for the minimum latency problem, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.152-158, January 28-30, 1996, Atlanta, Georgia, United States
 
19
T.E. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38 (1985), pp. 293-306.
 
20
John A. Hartigan, Clustering Algorithms, John Wiley & Sons, Inc., New York, NY, 1975
 
21
Dorit S. Hochbaum, Various notions of approximations: good, better, best, and more, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
22
Dorit S. Hochbaum , Wolfgang Maass, Approximation schemes for covering and packing problems in image processing and VLSI, Journal of the ACM (JACM), v.32 n.1, p.130-136, Jan. 1985  [doi>10.1145/2455.214106]
 
23
D.S. Hochbaum and D.B. Shmoys. A best possible heuristic for the k-center problem. Mathematics of Operations Research, 10 (1985), pp. 180-184.
24
Dorit S. Hochbaum , David B. Shmoys, A unified approach to approximation algorithms for bottleneck problems, Journal of the ACM (JACM), v.33 n.3, p.533-550, July 1986  [doi>10.1145/5925.5933]
 
25
S. lrani and A. Karlin. Online Computation. In: D.S. Hochbaum, editor, Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, 1996.
 
26
N. Jardine and C.J. van Rijsbergen. The Use of Hierarchical Clustering in Information Retrieval. Information Storage and Retrieval, 7 (1971), pp. 217-240.
 
27
Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
 
28
O. Kariv and S.L. Hakimi. An algorithmic approach to network location problems, part i: the p-centers problem. SIAM Journal of Applied Mathematics, 37 (1979), pp. 513-538.
 
29
N. Megiddo and K.J. Supowit. On the complexity of some common geometric problems. SIAM Journal on Computing, 13 (1984), pp. 182-196.
 
30
S.G. Mentzer. Lower bounds on metric k-center problems. Manuscript, 1988.
 
31
Rajeev Motwani , Steven Phillips , Eric Torng, Non-clairvoyant scheduling, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.422-431, January 25-27, 1993, Austin, Texas, United States
 
32
Edward Omiecinski , Peter Scheuermann, A global approach to record clustering and file reorganization, Proc. of the third joint BCS and ACM symposium on Research and development in information retrieval, p.201-219, November 1984, King's College, Cambridge
 
33
J. Pach and P.K. Agarwal. Combinatorial Geometry. John Wiley & Sons, New York, NY, 1995.
 
34
Edie Rasmussen, Clustering algorithms, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
 
35
C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
 
36
C. Rogers. A note on coverings. Mathematika, 4 (1957), pp. 11-6.
 
37
Gerald Salton, Automatic text processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
 
38
Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
 
39
Peter Willett, Recent trends in hierarchic document clustering: a critical review, Information Processing and Management: an International Journal, v.24 n.5, p.577-597, 1988  [doi>10.1016/0306-4573(88)90027-1]
 
40
Ian H. Witten , Alistair Moffat , Timothy C. Bell, Managing gigabytes (2nd ed.): compressing and indexing documents and images, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999

CITED BY  56
Moses Charikar , Rina Panigrahy, Clustering to minimize the sum of cluster diameters, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.1-10, July 2001, Hersonissos, Greece
Javed Aslam , Katya Pelekhov , Daniela Rus, Using star clusters for filtering, Proceedings of the ninth international conference on Information and knowledge management, p.306-313, November 06-11, 2000, McLean, Virginia, United States
Nina Mishra , Dan Oblinger , Leonard Pitt, Sublinear time approximate clustering, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.439-447, January 07-09, 2001, Washington, D.C., United States
Allan Borodin , Morten N. Nielsen , Charles Rackoff, (Incremental) priority algorithms, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.752-761, January 06-08, 2002, San Francisco, California
Eddie C. Shek , Son K. Dao , Yongguang Zhang , Darrel J. Van Buer , Giovanni Giuffrida, Intelligent information dissemination services in hybrid satellite-wireless networks, Mobile Networks and Applications, v.5 n.4, p.273-284, Dec. 2000
Eddie C. Shek , Son K. Dao , Yongguang Zhang , Darrel Van Buer, Dynamic multicast information dissemination in hybrid satellite-wireless networks, Proceedings of the 1st ACM international workshop on Data engineering for wireless and mobile access, p.30-35, August 20-20, 1999, Seattle, Washington, United States
Son Dao , Eddie Shek , Asha Vellaikal , Richard R. Muntz , Lixia Zhang , Miodrag Potkonjak , Ouri Wolfson, Semantic multicast: intelligently sharing collaborative sessions, ACM Computing Surveys (CSUR), v.31 n.2es, June 1999
Gabriel L. Somlo , Adele E. Howe, Incremental clustering for profile maintenance in information gathering web agents, Proceedings of the fifth international conference on Autonomous agents, p.262-269, May 2001, Montreal, Quebec, Canada
Alois Ferscha , James Johnson, Shock resistant Time Warp, Proceedings of the thirteenth workshop on Parallel and distributed simulation, p.92-100, May 01-04, 1999, Atlanta, Georgia, United States
Srinivas Doddi , Madhav V. Marathe , S. S. Ravi , David Scot Taylor , Peter Widmayer, Approximation algorithms for clustering to minimize the sum of diameters, Nordic Journal of Computing, v.7 n.3, p.185-203, Fall 2000
Pankaj K. Agarwal , Micha Sharir, Efficient algorithms for geometric optimization, ACM Computing Surveys (CSUR), v.30 n.4, p.412-458, Dec. 1998
P. W. Finn , L. E. Kavraki , J.-C. Latombe , R. Motwani , C. Shelton , S. Venkatasubramanian , A. Yao, RAPID: randomized pharmacophore identification for drug design, Proceedings of the thirteenth annual symposium on Computational geometry, p.324-333, June 04-06, 1997, Nice, France
Pankaj K. Agarwal , Cecilia M. Procopiuc, Exact and approximation algorithms for clustering, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.658-667, January 25-27, 1998, San Francisco, California, United States
Kyoung-Mi Lee , W. Nick Street, Incremental feature weight learning and its application to a shape-based query system, Pattern Recognition Letters, v.23 n.7, p.865-874, May 2002
Deok-Hwan Kim , Chin-Wan Chung, QCluster: relevance feedback using adaptive clustering for content-based image retrieval, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
Venkatesh Ganti , Raghu Ramakrishnan, Mining and monitoring evolving data, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
Moses Charikar , Liadan O'Callaghan , Rina Panigrahy, Better streaming algorithms for clustering problems, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
Erhan Gokcay , Jose C. Principe, Information Theoretic Clustering, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.2, p.158-171, February 2002
Sudipto Guha , Adam Meyerson , Nina Mishra , Rajeev Motwani , Liadan O'Callaghan, Clustering Data Streams: Theory and Practice, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.515-528, March 2003
Gabriel L. Somlo , Adele E. Howe, Using web helper agent profiles in query generation, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia
Andreea B. Dragut , Codrin M. Nichitiu, A Monotonic On-Line Linear Algorithm for Hierarchical Agglomerative Classification, Information Technology and Management, v.5 n.1-2, p.111-141, January-April 2004
Nina Mishra , Dana Ron , Ram Swaminathan, A New Conceptual Clustering Framework, Machine Learning, v.56 n.1-3, p.115-151
Fang Wang, Self-organising communities formed by middle agents, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 3, July 15-19, 2002, Bologna, Italy
Javed Aslam , Katya Pelekhov , Daniela Rus, Static and dynamic information organization with star clusters, Proceedings of the seventh international conference on Information and knowledge management, p.208-217, November 02-07, 1998, Bethesda, Maryland, United States
Javed Aslam , Katya Pelekhov , Daniela Rus, A practical clustering algorithm for static and dynamic information organization, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.51-60, January 17-19, 1999, Baltimore, Maryland, United States
Ravi Kannan , Santosh Vempala , Adrian Vetta, On clusterings: Good, bad and spectral, Journal of the ACM (JACM), v.51 n.3, p.497-515, May 2004
Samer Nassar , Jörg Sander , Corrine Cheng, Incremental and effective data summarization for dynamic hierarchical clustering, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
Moses Charikar , Rina Panigrahy, Clustering to minimize the sum of cluster diameters, Journal of Computer and System Sciences, v.68 n.2, p.417-441, March 2004
Khaled M. Hammouda , Mohamed S. Kamel, Efficient Phrase-Based Document Indexing for Web Document Clustering, IEEE Transactions on Knowledge and Data Engineering, v.16 n.10, p.1279-1296, October 2004
Adam Meyerson , Liadan O'Callaghan , Serge Plotkin, A k-Median Algorithm with Running Time Independent of Data Size, Machine Learning, v.56 n.1-3, p.61-87
Gereon Frahling , Christian Sohler, Coresets in dynamic geometric data streams, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
David Cheng , Santosh Vempala , Ravi Kannan , Grant Wang, A divide-and-merge methodology for clustering, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland
Ali Shokoufandeh , Spiros Mancoridis , Trip Denton , Matthew Maycock, Spectral and meta-heuristic algorithms for software clustering, Journal of Systems and Software, v.77 n.3, p.213-223, September 2005
Deok-Hwan Kim , Chin-Wan Chung , Kobus Barnard, Relevance feedback using adaptive clustering for image similarity retrieval, Journal of Systems and Software, v.78 n.1, p.9-23, October 2005
Kevin L. Chang , Ravi Kannan, The space complexity of pass-efficient algorithms for clustering, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1157-1166, January 22-26, 2006, Miami, Florida
Sanjoy Dasgupta , Philip M. Long, Performance guarantees for hierarchical clustering, Journal of Computer and System Sciences, v.70 n.4, p.555-569, June 2005
Marek Chrobak , Claire Kenyon , Neal Young, The reverse greedy algorithm for the metric k-median problem, Information Processing Letters, v.97 n.2, p.68-72, 31 January 2006
Ching-Huang Yun , Kun-Ta Chuang , Ming-Syan Chen, Adherence clustering: an efficient method for mining market-basket clusters, Information Systems, v.31 n.3, p.170-186, May 2006
Xun Yue , Hongwei Mo , Zhong-Xian Chi, Immune-inspired incremental feature selection technology to data streams, Applied Soft Computing, v.8 n.2, p.1041-1049, March, 2008
S. Muthukrishnan, Data streams: algorithms and applications, Foundations and Trends® in Theoretical Computer Science, v.1 n.2, p.117-236, August 2005
Dimitris Fotakis, Incremental algorithms for facility location and k-Median, Theoretical Computer Science, v.361 n.2, p.275-313, 1 September 2006
Marek Chrobak , Claire Kenyon-Mathieu, SIGACT news online algorithms column 10: competitiveness via doubling, ACM SIGACT News, v.37 n.4, December 2006
David Cheng , Ravi Kannan , Santosh Vempala , Grant Wang, A divide-and-merge methodology for clustering, ACM Transactions on Database Systems (TODS), v.31 n.4, p.1499-1525, December 2006
Yanling Chi , Maylor K. H. Leung, ALSBIR: A local-structure-based image retrieval, Pattern Recognition, v.40 n.1, p.244-261, January, 2007
Flip Korn , S. Muthukrishnan , Divesh Srivastava, Reverse nearest neighbor aggregates over data streams, Proceedings of the 28th international conference on Very Large Data Bases, p.814-825, August 20-23, 2002, Hong Kong, China
Yunjae Jung , Haesun Park , Ding-Zhu Du , Barry L. Drake, A Decision Criterion for the Optimal Number of Clusters in Hierarchical Clustering, Journal of Global Optimization, v.25 n.1, p.91-111, January 2003
Yun Chi , Xiaodan Song , Dengyong Zhou , Koji Hino , Belle L. Tseng, Evolutionary spectral clustering by incorporating temporal smoothness, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA
Kyoung-Mi Lee, Component-based face detection and verification, Pattern Recognition Letters, v.29 n.3, p.200-214, February, 2008
Byron J. Gao , Martin Ester , Jin-Yi Cai , Oliver Schulte , Hui Xiong, The minimum consistent subset cover problem and its applications in data mining, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA
Jun-Peng Bao , Jun-Yi Shen , Xiao-Dong Liu , Hai-Yan Liu, The heavy frequency vector-based text clustering, International Journal of Business Intelligence and Data Mining, v.1 n.1, p.42-53, July 2005
Paraskevas Orfanidis , David J. Russomanno, Preprocessing enhancements to improve data mining algorithms, International Journal of Business Intelligence and Data Mining, v.3 n.2, p.196-211, September 2008
Gang Luo , Chunqiang Tang , Hao Yang , Xing Wei, MedSearch: a specialized search engine for medical information retrieval, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA
Kun-Ta Chuang , Keng-Pei Lin , Ming-Syan Chen, Quality-Aware Sampling and Its Applications in Incremental Data Mining, IEEE Transactions on Knowledge and Data Engineering, v.19 n.4, p.468-484, April 2007
Sudipto Guha, Tight results for clustering and summarizing data streams, Proceedings of the 12th International Conference on Database Theory, March 23-25, 2009, St. Petersburg, Russia
Roman Y. Shtykh , Qun Jin, Dynamically constructing user profiles with similarity-based online incremental clustering, International Journal of Advanced Intelligence Paradigms, v.1 n.4, p.377-397, June 2009
Alireza Rezaei Mahdiraji, Clustering data stream: A survey of algorithms, International Journal of Knowledge-based and Intelligent Engineering Systems, v.13 n.2, p.39-44, April 2009

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms


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

Collaborative Colleagues:
Moses Charikar: colleagues
Chandra Chekuri: colleagues
Tomás Feder: colleagues
Rajeev Motwani: 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