On the Average Number of Maxima in a Set of Vectors and Applications

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

On the Average Number of Maxima in a Set of Vectors and Applications

Full text

Pdf (436 KB)

Source

Journal of the ACM (JACM) archive
Volume 25 , Issue 4 (October 1978) table of contents

Pages: 536 - 543

Year of Publication: 1978

ISSN:0004-5411

Authors

J. L. Bentley	Department of Computer Science, Carnegie-Mellon University, Pittsburgh, PA
H. T. Kung	Department of Computer Science, Carnegie-Mellon University, Pittsburgh, PA
M. Schkolnick	IBM Research Laboratory, San Jose, CA
C. D. Thompson	Department of Computer Science, Carnegie-Mellon University, Pittsburgh, PA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 96, Citation Count: 41

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/322092.322095 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	BENTLEY, J L, AND SHAMOS, M I Divide and conquer for linear expected tune Inform Processing Letters 7, 2 (February 1978), 87-91
	2	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	3	H. T. Kung , F. Luccio , F. P. Preparata, On Finding the Maxima of a Set of Vectors, Journal of the ACM (JACM), v.22 n.4, p.469-476, Oct. 1975 [doi>10.1145/321906.321910]
	4	Lur~s, J A Efficient algorithms for the partmonmg of trees IBM J Res Develop 18, 3 (May 1974), 217-224
	5	MOroN, T L, AND MARSTEN, R E An algorithm for nonlinear knapsack problems. Manage Sc). 22, l0 (1976), 1147-1158
	6	SANTALO) L A Encyclopedm of Mathematics and Its Apphcanons, Vol 1 Integral Geometry and Geometric Probablhty Addison-Wesley, Reading, Mass, 1976
	7	A clustering algorithm for hierarchical structures, ACM Transactions on Database Systems (TODS), v.2 n.1, p.27-44, March 1977 [doi>10.1145/320521.320531]
	8	SCHKOLNICK, M, AND THOMPSON, C D A clustering strategy for relational data bases. 1977 To appear
	9	YAO, F F On finding the maximal elements m a set of plane vectors Rep UIUCDCS-R-74-667, Comptr Scl. Dept., U. of lllmols, Urbana, Ill., July 1974

CITED BY 41

	Timothy M. Chan, Output-sensitive results on convex hulls, extreme points, and related problems, Proceedings of the eleventh annual symposium on Computational geometry, p.10-19, June 05-07, 1995, Vancouver, British Columbia, Canada
	Mordecai J. Golin, Maxima in convex regions, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.352-360, January 25-27, 1993, Austin, Texas, United States
	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
	Ronald Prescott Loui, Optimal paths in graphs with stochastic or multidimensional weights, Communications of the ACM, v.26 n.9, p.670-676, Sept. 1983
	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
	R. Miller , Q. F. Stout, Computational geometry on hypercube computers, Proceedings of the third conference on Hypercube concurrent computers and applications, p.1220-1229, January 1989, Pasadena, California, United States
	Bernard Chazelle, Lower bounds for orthogonal range searching: part II. The arithmetic model, Journal of the ACM (JACM), v.37 n.3, p.439-463, July 1990
	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
	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
	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
	Christian Ronse, A Bibliography on Digital and Computational Convexity (1961-1988), IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.2, p.181-190, February 1989
	Zhi-Dong Bai , Luc Devroye , Hsien-Kuei Hwang , Tsung-Hsi Tsai, Maxima in hypercubes, Random Structures & Algorithms, v.27 n.3, p.290-309, October 2005
	Pak K. Chan , Martine D. F. Schlag , Clark D. Thomborson , Vojin G. Oklobdzija, Delay Optimization of Carry-Skip Adders and Block Carry-Lookahead Adders Using Multidimensional Dynamic Programming, IEEE Transactions on Computers, v.41 n.8, p.920-930, August 1992
	Olivier Teytaud, On the hardness of offline multi-objective optimization, Evolutionary Computation, v.15 n.4, p.475-491, Winter 2007
	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
	Yishan Jiao, Maintaining stream statistics over multiscale sliding windows, ACM Transactions on Database Systems (TODS), v.31 n.4, p.1305-1334, December 2006
	Vladlen Koltun , Christos H. Papadimitriou, Approximately dominating representatives, Theoretical Computer Science, v.371 n.3, p.148-154, March, 2007
	David W. Corne , Joshua D. Knowles, Techniques for highly multiobjective optimisation: some nondominated points are better than others, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England
	Raymond Chi-Wing Wong , Jian Pei , Ada Wai-Chee Fu , Ke Wang, Mining favorable facets, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, 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
	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
	Zhenglu Yang , Lin Li , Botao Wang , Masaru Kitsuregawa, Towards efficient dominant relationship exploration of the product items on the web, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada
	Haim Kaplan , Natan Rubin , Micha Sharir , Elad Verbin, Counting colors in boxes, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.785-794, January 07-09, 2007, New Orleans, Louisiana
	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
	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
	Sumit Ganguly, Design and Analysis of Parametric Query Optimization Algorithms, Proceedings of the 24rd International Conference on Very Large Data Bases, p.228-238, August 24-27, 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
	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
	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
	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
	Youngdae Kim , Gae-Won You , Seung-Won Hwang, Ranking strategies and threats: a cost-based pareto optimization approach, Distributed and Parallel Databases, v.26 n.1, p.127-150, August 2009
	Jun-Seok Heo , Kyu-Young Whang , Min-Soo Kim , Yi-Reun Kim , Il-Yeol Song, The partitioned-layer index: Answering monotone top-k queries using the convex skyline and partitioning-merging technique, Information Sciences: an International Journal, v.179 n.19, p.3286-3308, September, 2009
	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
	L. Mandow , L. Mandow , J. L. P´erez De la Cruz , J. L. P´erez De la Cruz, A new approach to multiobjective A* search, Proceedings of the 19th international joint conference on Artificial intelligence, p.218-223, July 30-August 05, 2005, Edinburgh, Scotland
	Parisa Haghani , Sebastian Michel , Karl Aberer, Evaluating top-k queries over incomplete data streams, Proceeding of the 18th ACM conference on Information and knowledge management, November 02-06, 2009, Hong Kong, China
	Jongwuk Lee , Seung-won Hwang, SkyTree: scalable skyline computation for sensor data, Proceedings of the Third International Workshop on Knowledge Discovery from Sensor Data, June 28-28, 2009, Paris, France