Сотрудники :: Гасанов Эльяр Эльдарович :: Публикации Гасанова Э.Э.
Instantly solvable search problems
Eljar E. Gasanov
Moscow State University
This paper deals with the investigation of search time in database.
The search time is very important parameter for many information
systems (for example, the real-time systems).
Thus, the problem of construction of algorithms
minimizing the search time for the concrete information system is
The new very fast on the average algorithms are suggested in the
paper. These algorithms solve some geometric search problems.
The estimations for the time complexity of these algorithms are
Database theory; information search complexity; information
search modelling; fast algorithms.
There are two approaches to construction of algorithms
solving information search problems.
The first approach supposes the creation of universal algorithms
having wide range of application. Usually this universality
leads to some loss of efficiency. The second approach
supposes the creation of effective algorithms but these
algorithms can be used in a narrow range.
Both approaches have a right to
existence. Usually the universal algorithms of organization and
search of data are used in the database systems, intended for
extensive commercial application. When the efficiency of the
universal algorithms do not satisfies in some special
databases then the necessity of construction of special data
organization and search algorithms appears. On the other
hand availability of the great number of effective algorithms,
which can be used in the various situations, can allow to realize
the third approach.
This approach consists in
the creation of an expert system, which can
help for each search problem to find suitable effective
algorithms from available ones in the expert system database.
Thus, the third approach unites advantages of the first and
second ones: on the one hand it can ensure applicability for a
wide class of problems but on the other hand it can ensure high
efficiency. Perspective of the third approach increases the
importance of effective algorithms construction in spite of
the narrowness of their application.
In this paper the search algorithms efficiency means the
average search time. The average search time is very important
parameter for all real-time systems. Therefore the problem of
construction of fast search algorithms is very actual.
Two new algorithms for solving two geometric search problems
are suggested in the paper.
These algorithms can be very useful for computer-aided design
and computer graphics systems.
Data is analysed and pre-processed before using
the data by search algorithm. These steps are doing
to achieve the optimal time of the search.
BASIC NOTIONS AND RESULTS
The following mathematical model of information
search problem is suggested in the paper .
Let and be some sets. Call a set of queries
and a set of objects to be found (or required objects).
Let be a relation
on , which we call search relation. Say a
satisfies query if .
Let be some finite subset of .
an information search problem (ISP).
consists in enumeration for any query
all that and only that objects , such that
be a probability space
under , where is the algebra of subsets of ,
is probability measure on .
Let be some algorithm, which solves ISP .
is solving time of by on query .
– average solving time of .
, where is taken on the set of
all algorithms, solving problem .
A new mathematical model of the search algorithm was introduced
by the author (Gasanov, 1991). The notions of algorithm,
which solves ISP , and values and can be
formal defined in this model. But we do not describe this model
because the limit of space do not allow to do it. We notice
only that some schemes are corresponded to the search algorithms,
and these schemes are directed graphs. The required objects from
are corresponded to some nodes of this graph, and some
special functions are corresponded to edges or nodes of the
graph. The range of definition of these functions is the set of
queries X. The complexity of these schemes is defined so that
it reflects the average search time of correspondent algorithms.
The following theorems are obtained.
For any ISP
is an instantly solvable
search problem if
there exist algorithm , solving , such that
where is a constant, independent of number of elements
of set V.
Let for each
probability density function, and
called problem of search of
identical objects) is instantly solvable search problem, and
– relation on
such that for
Let for each
probability density function, and
(which is called
interval search problem)
is instantly solvable search problem, and
JUSTIFICATION OF THE RESULTS
Since we do not describe the mathematical model of the search
algorithms we cannot give the formal proof of the above theorems.
Therefore we give only the proof ideas and algorithms description.
The first theorem say that the average search time is not less
than the average time of the answer enumeration. It is the evident
and well known fact.
The result of the second theorem is founded on the following
is our ordered set of the objects
to be found.
Let be some query.
On the first step we calculate the number .
If then . Therefore on the second step
we do binary search in the set (if
The estimation of the theorem 2 is based on the fact that the
worst on the average situations is the case when
. The last fact follows from the
concavity of the logarithm function.
When the result of the third theorem is grounded on
is our increasing ordered set of
the objects to be found.
Let be some query from .
On the first step we calculate the value .
with the help of the binary search. Then we look through
the objects from left to right beginning from
we calculate the value
Therefore we will look through the objects
from left to right beginning from while
(we will do it only if ).
Then we will look through the objects from
right to left beginning from while
(if we will begin from ).
Finally notice that
whence it follows the result of the
theorem 3 under condition .
The case is proved by the method of dimension reduction.
The above-mentioned search problems are well known and widespread
geometric search problems. They are used in the all computer
graphics systems and CAD. For example, every time we are looking
for points located in some window we deal with the 2-dimensional
interval search problem.
The first above search problem is typical representative of problem
of search of identical objects, which occur in the all database
systems. Under certain conditions above algorithms can be used easily
for solving of the well known key search problem. Therefore the
results of this paper can be used in the large class of
information search systems when the search time is critical
Gasanov E.E. (1991); On one mathematical model of
Discrete mathematics, v. 3, No 2 (pp. 69-76) (in Russian).
Proceedings of International Symposium on Intelligent Data Analysis (IDA-95). Baden-Baden, Germany. HAS Press, 1995.