article

Free access

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

Authors:

J. L. Bentley,

H. T. Kung,

M. Schkolnick,

C. D. ThompsonAuthors Info & Claims

Journal of the ACM (JACM), Volume 25, Issue 4

Pages 536 - 543

https://doi.org/10.1145/322092.322095

Published: 01 October 1978 Publication History

PDF eReader

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

Google Scholar

[2]

KNUTH, D E The Art of Computer Programming, Vol 1 Fundamental Algorithms. Addison-Wesley, Reading, Mass, 1973.

Crossref

Google Scholar

[3]

KUNG, H.T, LuccIo, F., AND PREPARATA, F P On f'mdmg the maxuna of a set of vectors. J. A CM 22, 4 (Oct 1975), 469-476.

Crossref

Google Scholar

[4]

Lur~s, J A Efficient algorithms for the partmonmg of trees IBM J Res Develop 18, 3 (May 1974), 217-224

Google Scholar

[5]

MOroN, T L, AND MARSTEN, R E An algorithm for nonlinear knapsack problems. Manage Sc). 22, l0 (1976), 1147-1158

Google Scholar

[6]

SANTALO) L A Encyclopedm of Mathematics and Its Apphcanons, Vol 1 Integral Geometry and Geometric Probablhty Addison-Wesley, Reading, Mass, 1976

Google Scholar

[7]

SCHKOLNICK, M. A clustenng algonthm for hlerarchtcal structures A CM Trans Database Syst. 2, l (March 1977), 27-44

Crossref

Google Scholar

[8]

SCHKOLNICK, M, AND THOMPSON, C D A clustering strategy for relational data bases. 1977 To appear

Google Scholar

[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

Google Scholar

Cited By

View all

Huang Y(2025)Distributed MapReduce processing of location-based aggregate queries in road networksDistributed and Parallel Databases10.1007/s10619-024-07448-243:1Online publication date: 1-Dec-2025
https://dl.acm.org/doi/10.1007/s10619-024-07448-2
Lai CLin HLiu C(2024)Distributed Indexing Schemes for K-Dominant Skyline Analytics on Uncertain Edge-IoT DataIEEE Transactions on Emerging Topics in Computing10.1109/TETC.2023.332629512:3(878-890)Online publication date: Jul-2024
https://doi.org/10.1109/TETC.2023.3326295
Huang YLee C(2024)Efficient processing of all neighboring object group queries with budget range constraint in road networksComputing10.1007/s00607-024-01260-7106:5(1359-1393)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1007/s00607-024-01260-7
Show More Cited By

Index Terms

On the Average Number of Maxima in a Set of Vectors and Applications
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

On the average number of maxima in a set of vectors
A New Signal Denoising Algorithm from Wavelet Modulus Maxima
FSKD '07: Proceedings of the Fourth International Conference on Fuzzy Systems and Knowledge Discovery - Volume 03

In this paper, a new signal denoising algorithm from wavelet transform modulus maxima (WTMM) is proposed. It essentially combines Mallat's multiresolution analysis(MRA) theory and Donoho's denoising approach. With WTMM, we can improve the signal ...
Reducing SVR Support Vectors by Using Backward Deletion
KES '08: Proceedings of the 12th international conference on Knowledge-Based Intelligent Information and Engineering Systems, Part III

Support Vector Regression (SVR) is one of the most famous sparse kernel machines which inherits many advantages of Support Vector Machines (SVM). However, since the number of support vectors grows rapidly with the increase of training samples, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 25, Issue 4

Oct. 1978

172 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/322092

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1978

Published in JACM Volume 25, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

341
Total Citations
View Citations
1,268
Total Downloads

Downloads (Last 12 months)113
Downloads (Last 6 weeks)29

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Huang Y(2025)Distributed MapReduce processing of location-based aggregate queries in road networksDistributed and Parallel Databases10.1007/s10619-024-07448-243:1Online publication date: 1-Dec-2025
https://dl.acm.org/doi/10.1007/s10619-024-07448-2
Lai CLin HLiu C(2024)Distributed Indexing Schemes for K-Dominant Skyline Analytics on Uncertain Edge-IoT DataIEEE Transactions on Emerging Topics in Computing10.1109/TETC.2023.332629512:3(878-890)Online publication date: Jul-2024
https://doi.org/10.1109/TETC.2023.3326295
Huang YLee C(2024)Efficient processing of all neighboring object group queries with budget range constraint in road networksComputing10.1007/s00607-024-01260-7106:5(1359-1393)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1007/s00607-024-01260-7
Rahman MAzharul Hasan K(2024)Computing Skyline Query on Incomplete DataProceedings of the 2nd International Conference on Big Data, IoT and Machine Learning10.1007/978-981-99-8937-9_44(657-672)Online publication date: 30-Mar-2024
https://doi.org/10.1007/978-981-99-8937-9_44
Akram WSaxena S(2024)Maximizing Weighted Dominance in the PlaneTheoretical Aspects of Computing – ICTAC 202410.1007/978-3-031-77019-7_9(153-163)Online publication date: 22-Nov-2024
https://doi.org/10.1007/978-3-031-77019-7_9
Phan-Luong V(2024)Mining Interesting Aggregate TuplesIntelligent Systems and Applications10.1007/978-3-031-47715-7_16(229-243)Online publication date: 30-Jan-2024
https://doi.org/10.1007/978-3-031-47715-7_16
Mouratidis K(2023)Opportunities for spatial database research in the context of preference queriesProceedings of the 7th ACM SIGSPATIAL Workshop on Location-based Recommendations, Geosocial Networks and Geoadvertising10.1145/3615896.3628418(1-3)Online publication date: 13-Nov-2023
https://dl.acm.org/doi/10.1145/3615896.3628418
Cohen EMiller RSarraf EStout Q(2023)Efficient convexity and domination algorithms for fine- and medium-grain hypercube computersAlgorithmica10.1007/BF017587517:1-6(51-75)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1007/BF01758751
Coello Coello C(2023)Recent Research Topics in Evolutionary Multiobjective Optimization: A Personal PerspectiveComputational Intelligence10.1007/978-3-031-46221-4_5(90-120)Online publication date: 3-Nov-2023
https://doi.org/10.1007/978-3-031-46221-4_5
Zhang ZWen JCai XCui Z(2023)A many‐objective optimization algorithm with dual criteria and mixed distribution correction strategyConcurrency and Computation: Practice and Experience10.1002/cpe.770435:21Online publication date: 30-Mar-2023
https://doi.org/10.1002/cpe.7704
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations