On Finding the Maxima of a Set of Vectors

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On Finding the Maxima of a Set of Vectors

Full text

Pdf (464 KB)

Source

Journal of the ACM (JACM) archive
Volume 22 , Issue 4 (October 1975) table of contents

Pages: 469 - 476

Year of Publication: 1975

ISSN:0004-5411

Authors

H. T. Kung	Department of Computer Science, Carnegie-Mellon University, Schenley Park, Pittsburgh, PA
F. Luccio	Istituto di Scienze dell'Informazione, Università di Pisa, 56100 Pisa, Italy
F. P. Preparata	Coordinated Science Laboratory, University of Illinois, Urbana, IL

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 26, Downloads (12 Months): 181, Citation Count: 68

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321906.321910 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	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	2	KUNG, H .T . On the computational complexity of finding the mamma of a set of vectors Proc 15th Annual IEEE Syrup. on Switching and Automata Theory, Oct. 1974, pp. 117-121 (also available as a Comput. Scl Dep. Rep, Carnegm-Mellon U , Pittsburgh, Pa , April 1974).
	3	LUCCIO, F., AND PREPARATA, F .P . Oil finding the maxima of a set of vectors. Istituto di Scienze dell'Informazione, UniversitA di Pisa, 56100 Pisa, Italy, Dec. 1973
	4	YAO, F. F On finding the maximal elements in a set of plane vectors Comput. Sci. Dep Rep, U. of Illinois at Urbana- Champaign, Urbana, Ill., July 1974.

CITED BY 68

	Peter F. Stadler , Christoph Flamm, Barrier Trees on Poset-Valued Landscapes, Genetic Programming and Evolvable Machines, v.4 n.1, p.7-20, March 2003
	Mark H. Overmars , Jan van Leeuwen, Dynamically maintaining configurations in the plane (Detailed Abstract), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.135-145, April 28-30, 1980, Los Angeles, California, United States
	D. P. Dobkin , H. Edelsbrunner , M. H. Overmars, Searching for empty convex polygons, Proceedings of the fourth annual symposium on Computational geometry, p.224-228, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	J. L. Bentley , H. T. Kung , M. Schkolnick , C. D. Thompson, On the Average Number of Maxima in a Set of Vectors and Applications, Journal of the ACM (JACM), v.25 n.4, p.536-543, Oct. 1978
	John Lillis , Chung-Kuan Cheng, Timing optimization for multi-source nets: characterization and optimal repeater insertion, Proceedings of the 34th annual conference on Design automation, p.214-219, June 09-13, 1997, Anaheim, California, United States
	F. P. Preparata , S. J. Hong, Convex hulls of finite sets of points in two and three dimensions, Communications of the ACM, v.20 n.2, p.87-93, Feb. 1977
	Sanjiv Kapoor, Dynamic maintenance of maximas of 2-d point sets, Proceedings of the tenth annual symposium on Computational geometry, p.140-149, June 06-08, 1994, Stony Brook, New York, United States
	Haklin Kimm, Two dimensional maximal elements problem on a reconfigurable optical pipelined bus system, Proceedings of the 1998 ACM symposium on Applied Computing, p.623-627, February 27-March 01, 1998, Atlanta, Georgia, United States
	Shlomo Moran , Marc Snir , Udi Manber, Applications of Ramsey's theorem to decision tree complexity, Journal of the ACM (JACM), v.32 n.4, p.938-949, Oct. 1985
	Harold N. Gabow , Jon Louis Bentley , Robert E. Tarjan, Scaling and related techniques for geometry problems, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.135-143, December 1984
	Dan E. Willard , George S. Lueker, Adding range restriction capability to dynamic data structures, Journal of the ACM (JACM), v.32 n.3, p.597-617, July 1985
	Jon L. Bentley , Kenneth L. Clarkson , David B. Levine, Fast linear expected-time alogorithms for computing maxima and convex hulls, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.179-187, January 22-24, 1990, San Francisco, California, United States
	B Chazelle , H Edelsbrunner, Linear data structures for two types of range search, Proceedings of the second annual symposium on Computational geometry, p.293-302, June 02-04, 1986, Yorktown Heights, New York, United States
	Victor Jon Griswold, Core algorithms for autonomous monitoring of distributed systems, ACM SIGPLAN Notices, v.26 n.12, p.36-45, Dec. 1991
	Young C. Wee , Seth Chaiken , Dan E. Willard, Computing geographic nearest neighbors using monotone matrix searching (preliminary version), Proceedings of the 1990 ACM annual conference on Cooperation, p.49-55, February 20-22, 1990, Washington, D.C., United States
	Jon Louis Bentley, Multidimensional divide-and-conquer, Communications of the ACM, v.23 n.4, p.214-229, April 1980
	Jon Louis Bentley , Michael Ian Shamos, Divide-and-conquer in multidimensional space, Proceedings of the eighth annual ACM symposium on Theory of computing, p.220-230, May 03-05, 1976, Hershey, Pennsylvania, United States
	M J Atallah , M T Goodrich, Efficient plane sweeping in parallel, Proceedings of the second annual symposium on Computational geometry, p.216-225, June 02-04, 1986, Yorktown Heights, New York, United States
	Mikhail J. Atallah , Michael T. Goodrich , Kumar Ramaiyer, Biased finger trees and three-dimensional layers of maxima: (preliminary version), Proceedings of the tenth annual symposium on Computational geometry, p.150-159, June 06-08, 1994, Stony Brook, New York, United States
	Sandeep Sen , Neelima Gupta, Distribution-sensitive algorithms, Nordic Journal of Computing, v.6 n.2, p.194-211, Summer 1999
	Dimitris Papadias , Yufei Tao , Greg Fu , Bernhard Seeger, An optimal and progressive algorithm for skyline queries, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
	Jon Louis Bentley , Dorothea Haken , James B. Saxe, A general method for solving divide-and-conquer recurrences, ACM SIGACT News, v.12 n.3, Fall 1980
	Pin-Kwang Eng , Beng Chin Ooi , Kian-Lee Tan, Indexing for progressive skyline computation, Data & Knowledge Engineering, v.46 n.2, p.169-201, August 2003
	J. Mark Keil , Patrice Belleville, Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs, Discrete Applied Mathematics, v.140 n.1-3, p.73-89, 15 May 2004
	Keith Frikken , Mikhail Atallah , Marina Bykova, Remote revocation of smart cards in a private DRM system, Proceedings of the 2005 Australasian workshop on Grid computing and e-research, p.169-177, January 01, 2005, Newcastle, New South Wales, Australia
	Parke Godfrey , Ryan Shipley , Jarek Gryz, Maximal vector computation in large data sets, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	Chee-Yong Chan , Pin-Kwang Eng , Kian-Lee Tan, Stratified computation of skylines with partially-ordered domains, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	Dimitris Papadias , Yufei Tao , Greg Fu , Bernhard Seeger, Progressive skyline computation in database systems, ACM Transactions on Database Systems (TODS), v.30 n.1, p.41-82, March 2005
	Zhenjie Zhang , Xinyu Guo , Hua Lu , Anthony K. H. Tung , Nan Wang, Discovering strong skyline points in high dimensional spaces, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany
	Yidong Yuan , Xuemin Lin , Qing Liu , Wei Wang , Jeffrey Xu Yu , Qing Zhang, Efficient computation of the skyline cube, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	Jian Pei , Wen Jin , Martin Ester , Yufei Tao, Catching the best views of skyline: a semantic approach based on decisive subspaces, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	Georg Geyer , Christoph Kuhn , Beat Schmid, Designing a market for quantitative knowledge, International Journal of Electronic Commerce, v.1 n.4, p.89-107, June 1997
	Nick Koudas , Chen Li , Anthony K. H. Tung , Rares Vernica, Relaxing join and selection queries, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Dong Xin , Chen Chen , Jiawei Han, Towards robust indexing for ranked queries, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Nestoras Evmorfopoulos , Dimitris Karampatzakis , Georgios Stamoulis, Precise identification of the worst-case voltage drop conditions in power grid verification, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
	Jian Pei , Yidong Yuan , Xuemin Lin , Wen Jin , Martin Ester , Qing Liu , Wei Wang , Yufei Tao , Jeffrey Xu Yu , Qing Zhang, Towards multidimensional subspace skyline analysis, ACM Transactions on Database Systems (TODS), v.31 n.4, p.1335-1381, December 2006
	Zhenglu Yang , Botao Wang , Masaru Kitsuregawa, General dominant relationship analysis based on partial order models, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea
	Marc Geilen , Twan Basten, A calculator for Pareto points, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
	Salim Chowdhury , John Lillis, Repeater insertion for concurrent setup and hold time violations with power-delay trade-off, Proceedings of the 2007 international symposium on Physical design, March 18-21, 2007, Austin, Texas, USA
	Wolf-Tilo Balke , Ulrich Güntzer, Multi-objective query processing for database systems, Proceedings of the Thirtieth international conference on Very large data bases, p.936-947, August 31-September 03, 2004, Toronto, Canada
	Michael Morse , Jignesh M. Patel , H. V. Jagadish, Efficient skyline computation over low-cardinality domains, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	Donald Kossmann , Frank Ramsak , Steffen Rost, Shooting stars in the sky: an online algorithm for skyline queries, Proceedings of the 28th international conference on Very Large Data Bases, p.275-286, August 20-23, 2002, Hong Kong, China
	Cristina Bazgan , Hadrien Hugot , Daniel Vanderpooten, Solving efficiently the 0-1 multi-objective knapsack problem, Computers and Operations Research, v.36 n.1, p.260-279, January, 2009
	M. Morse , J. M. Patel , W. I. Grosky, Efficient continuous skyline computation, Information Sciences: an International Journal, v.177 n.17, p.3411-3437, September, 2007
	Cuiping Li , Anthony K. H. Tung , Wen Jin , Martin Ester, On dominating your neighborhood profitably, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	Tian Xia , Donghui Zhang, Refreshing the sky: the compressed skycube with efficient support for frequent updates, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
	Chee-Yong Chan , H. V. Jagadish , Kian-Lee Tan , Anthony K. H. Tung , Zhenjie Zhang, Finding k-dominant skylines in high dimensional space, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
	Ralf Hartmut Güting , Otto Nurmi , Thomas Ottmann, The direct dominance problem, Proceedings of the first annual symposium on Computational geometry, p.81-88, June 05-07, 1985, Baltimore, Maryland, United States
	David G. Kirkpatrick , Raimund Seidel, Output-size sensitive algorithms for finding maximal vectors, Proceedings of the first annual symposium on Computational geometry, p.89-96, June 05-07, 1985, Baltimore, Maryland, United States
	Parke Godfrey , Ryan Shipley , Jarek Gryz, Algorithms and analyses for maximal vector computation, The VLDB Journal — The International Journal on Very Large Data Bases, v.16 n.1, p.5-28, January 2007
	Kian-Lee Tan , Pin-Kwang Eng , Beng Chin Ooi, Efficient Progressive Skyline Computation, Proceedings of the 27th International Conference on Very Large Data Bases, p.301-310, September 11-14, 2001
	D. J. White, Epsilon Dominance and Constraint Partitioningin Multiple Objective Problems, Journal of Global Optimization, v.12 n.4, p.435-448, June 1998
	Jian Pei , Bin Jiang , Xuemin Lin , Yidong Yuan, Probabilistic skylines on uncertain data, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	Zhiyong Huang , Hua Lu , Beng Chin Ooi , Anthony K. H. Tung, Continuous Skyline Queries for Moving Objects, IEEE Transactions on Knowledge and Data Engineering, v.18 n.12, p.1645-1658, December 2006
	Jongwuk Lee , Gae-won You , IkChan Sohn , Seung-won Hwang , Kwangil Ko , Zino Lee, Supporting personalized top-k skyline queries using partial compressed skycube, Proceedings of the 9th annual ACM international workshop on Web information and data management, November 09-09, 2007, Lisbon, Portugal
	Sergey Bereg , J. Miguel Díaz-Báòez , Carlos Seara , Inmaculada Ventura, On finding widest empty curved corridors, Computational Geometry: Theory and Applications, v.38 n.3, p.154-169, October, 2007
	Marc Geilen , Twan Basten , Bart Theelen , Ralph Otten, An Algebra of Pareto Points, Fundamenta Informaticae, v.78 n.1, p.35-74, January 2007
	Hongbing Fang , Qian Wang , Yi-Cheng Tu , Mark F. Horstemeyer, An efficient non-dominated sorting method for evolutionary algorithms, Evolutionary Computation, v.16 n.3, p.355-384, Fall 2008
	Jongwuk Lee , Gae-won You , Seung-won Hwang, Personalized top-k skyline queries in high-dimensional space, Information Systems, v.34 n.1, p.45-61, March, 2009
	Bin Jiang , Jian Pei , Xuemin Lin , David W. Cheung , Jiawei Han, Mining preferences from superior and inferior examples, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA
	Raymond Chi-Wing Wong , Ada Wai-Chee Fu , Jian Pei , Yip Sing Ho , Tai Wong , Yubao Liu, Efficient skyline querying with variable user preferences on nominal attributes, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
	Dimitrios Skoutas , Dimitris Sacharidis , Alkis Simitsis , Verena Kantere , Timos Sellis, Top-k dominant web services under multi-criteria matching, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia
	Zhenjie Zhang , Laks V. S. Lakshmanan , Anthony K. H. Tung, On domination game analysis for microeconomic data mining, ACM Transactions on Knowledge Discovery from Data (TKDD), v.2 n.4, p.1-27, January 2009
	David Fuhry , Ruoming Jin , Donghui Zhang, Efficient skyline computation in metric space, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia
	Zhenjie Zhang , Yin Yang , Ruichu Cai , Dimitris Papadias , Anthony Tung, Kernel-based skyline cardinality estimation, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA
	Mikhail J. Atallah , Yinian Qi, Computing all skyline probabilities for uncertain data, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA
	Zhenglu Yang , Lin Li , Masaru Kitsuregawa, Efficient querying relaxed dominant relationship between product items based on rank aggregation, Proceedings of the 23rd national conference on Artificial intelligence, p.1261-1266, July 13-17, 2008, Chicago, Illinois
	Zhenglu Yang , Lin Li , Botao Wang , Masaru Kitsuregawa, Towards efficient dominant relationship exploration of the product items on the web, Proceedings of the 22nd national conference on Artificial intelligence, p.1483-1488, July 22-26, 2007, Vancouver, British Columbia, Canada