Abstract
In this paper, we investigate inverse problems of the interval query problem in application to data mining. Let I be the set of all intervals on U={0, 1, 2,., n}. Consider an objective function f(I), conditional functions u i(I) on I, and define an optimization problem of finding the interval I maximizing f(I) subject to u i(I) > K i for given real numbers K i (i=1, 2,., h). We propose efficient algorithms to solve the above optimization problem if the objective function is either additive or quotient, and the conditional functions are additive, where a function f is additive \(f\left( I \right) = \sum _{i \in I} \hat f\left( i \right)\) extending a function \(\hat f\) on U, and quotient if it is represented as a quotient of two additive functions. We use computational-geometric methods such as convex hull, range searching, and multidimensional divide-and-conquer.
Preview
Unable to display preview. Download preview PDF.
References
A. Aggarwal and J. Park, “Notes on Searching in Multidimensional Monotone Arrays”, Proc. 29th IEEE FOCS (1988) 497–512.
R. Agrawal, S. Ghosh, T. Imielinski, B. Iyer, and A. Swami: “An Interval Classifier for Database Mining Applications”, Proceedings of the 18th VLDB Conference, (1992) 560–573.
R. Agrawal, T. Imielinski and A. Swami, “Mining Association Rules between Sets of Items in Large Databases”, Proceedings of the ACM SIGMOD Conference on Management of Data, (1993) 207–216.
R. Agrawal and R. Srikant, “Fast Algorithms for Mining Association Rules”, Proceedings of the 20th VLDB Conference, (1994), 487–499.
J. L. Bentley, “Multidimensional divide-and-conquer”, CACM 23-4 (1980) 214–229.
J. L. Bentley, “Programming Pearls — Algorithm Design Techniques”, CACM 27-9 (1984), 865–871.
T. Fukuda, Y. Morimoto, S. Morishita, and T. Tokuyama, “Mining Optimized Association Rules for Numeric Attributes”, Proc. 15th ACM SIGACT-SIGMOD-SIGART Principle of Data Systems (1996), 182–191.
T. Fukuda, Y. Morimoto, S. Morishita, and T. Tokuyama, “Data Mining Using Two-Dimensional Optimized Association Rules: Scheme, Algorithms, and Visualization”, Proc. ACM SIGMOD Conference of Management of Data (1996), 13–23.
T. Fukuda, Y. Morimoto, S. Morishita, and T. Tokuyama, “SONAR: System for Optimized Numeric Association Rules (demonstration)”, Proc. ACM SIGMOD Conference on Management of Data (1996) p. 553.
H. T. Kung, F. Luccio, and F. P. Preparata, “On Finding the Maxima of a Set of Vectors”, JACM 22-4 (1975), 469–476.
N. Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms, J. ACM 30 (1983), 852–865.
J. S. Park and M.-S. Chen and P. S. Yu, “An Effective Hash-Based Algorithm for Mining Association Rules”, Proceedings of the ACM SIGMOD Conference on Management of Data, (1995), 175–186.
G. Piatetsky-Shapiro, “Discovery, Analysis, and Presentation of Strong Rules”, Knowledge Discovery in Databases, AAAI Press, (1991) 229–248.
F. P. Preparata and M. I. Shamos, Computational Geometry, an Introduction, 2nd edition (1988).
M. Stonebraker, R. Agrawal, U. Dayal, E. J. Neuhold and A. Reuter, “DBMS Research at a Crossroads: The Vienna Update”, Proceedings of the 19th VLDB Conference, (1993) 688–692.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fukuda, T., Morimoto, Y., Morishita, S., Tokuyama, T. (1996). Interval finding and its application to data mining. In: Asano, T., Igarashi, Y., Nagamochi, H., Miyano, S., Suri, S. (eds) Algorithms and Computation. ISAAC 1996. Lecture Notes in Computer Science, vol 1178. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0009481
Download citation
DOI: https://doi.org/10.1007/BFb0009481
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-62048-8
Online ISBN: 978-3-540-49633-5
eBook Packages: Springer Book Archive