2020

• Peter Poensgen, Ralf Möller: Branch-and-Bound Ranked Search by Minimizing Parabolic Polynomials
  in: Open J. Databases, 2020, Vol.7, (1), p.12-20
  
• Peter Poensgen, Ralf Möller: Quasi-Convex Scoring Functions in Branch-and-Bound Ranked Search
  in: Open Journal of Databases (OJDB), 2020, Vol.7, (1), p.1-11
  :

  @Article{OJDB_2020v7i1n01_Poensgen,
         author    = {Peter Poensgen and Ralf M{\"o}ller},
          title     = {{Quasi-Convex Scoring Functions in Branch-and-Bound Ranked Search}},
          journal   = {Open Journal of Databases (OJDB)},
          issn      = {2199-3459},
          year      = {2020},
          volume    = {7},
          number    = {1},
          pages     = {1--11},
          url       = {https://www.ronpub.com/ojdb/OJDB_2020v7i1n01_Poensgen.html},
          publisher = {RonPub},
          abstract = {For answering top-k queries in which attributes are aggregated to a scalar value for defining a ranking, usually the well-known branch-and-bound principle can be used for efficient query answering. Standard algorithms (e.g., Branch-and-Bound Ranked Search, BRS for short) require scoring functions to be monotone, such that a top-k ranking can be computed in sublinear time in the average case. If monotonicity cannot be guaranteed, efficient query answering algorithms are not known. To make branch-and-bound effective with descending or ascending rankings (maximum top-k or minimum top-k queries, respectively), BRS must be able to identify bounds for exploring search partitions, and only for monotonic ranking functions this is trivial. In this paper, we investigate the class of quasi-convex functions used for scoring objects, and we examine how bounds for exploring data partitions can correctly and efficiently be computed for quasi-convex functions in BRS for maximum top-k queries. Given that quasi-convex scoring functions can usefully be employed for ranking objects in a variety of applications, the mathematical findings presented in this paper are indeed significant for practical top-k query answering.}
      }