3
\$\begingroup\$

I am making a small library of metric data structures. That is data structures, which associate points in the n-dimensional space with objects and allow the user to find objects which are closest to a certain query with respect to a metric.

I have already implemented several data structures such as K-d trees, M-trees and R-trees, but they all have different interfaces. I am trying to factor out some common elements and make a common base interface for these data structures.

I am a beginner programmer and after I refactor my code I want to publish it for the first time in my life, hopefully for other users to use it. Therefore I would be grateful for any comments which can make the interface:

  1. more intuitive
  2. in line with best practices
  3. less likely to change in the future (since other people may be using it by then)
  4. taking advantage of C++11 (such as move semantics)

At the beginning there is a NearestNeighbors::Queue class which symbolizes a result of a search for k nearest neighbors. I use a separate class for this purpose, since in the future I may want to play with the implementation a little, since this is a performance critical part of the code. Currently it is implemented as a std::prioity_queue.

using Real = double;

namespace NearestNeighbors
{
template <class TPayload>
class Queue
{
public:
    Queue(std::size_t maxSize);

    typedef std::pair<Real, TPayload> Pair;
    Pair popMostDistant();

    Real highestDistance() const;
    std::size_t size() const;
private: 
    ...
};
}

The following template class serves as a base class to all my metric data structures.

namespace NearestNeighbors
{
template <typename TPayload, typename TVector = std::vector<Real>>
class Structure
{
public: 

    template <typename TIterator,
              typename TGetPosition,
              typename TGetPayload>
    Structure(TIterator begin,
              TIterator end,
              TGetPosition getPosition,
              TGetPayload getPayload);

    // Batch is used to store all payloads at a specific position.
    using Batch = std::list<TPayload>;

    const Batch& operator[] (const TVector& position) const;

    bool contains (const TVector& position, const TPayload& query) const;

    void insert   (const TVector& position, const TPayload& toInsert);
    void insert   (const TVector& position, const Batch& toInsert);
    // Maybe add interface to move-insert elements

    bool remove   (const TVector& position, const TPayload& toRemove);
    bool remove   (const TVector& position, const Batch& toRemove);
    bool remove   (const TVector& position);

    std::size_t computeSize() const;

    using Metric = Real (*)(const TVector&, const TVector&);         

    template <Metric metric = euclideanMetric>
    TPayload findFirstExactNearest(const TVector& position) const;

    template <Metric metric = euclideanMetric>
    const Batch& findExactNearest(const TVector& position) const;

    template <Metric metric = euclideanMetric>
    NearestNeighbors::Queue<TPayload> findExactKNN (const TVector& query,
                                                    std::size_t k) const;

    // The same interface for "findApproximateNearest"

private: 
    ...

};
} // namespace NearestNeighbors

An example of the usage could be a geographic system that looks up restaurants which are close to the user.

struct Restaurant
{
    std::string name;
    std::vector<Real> location;
};


int main()
{
    ...
    std::vector<Restaurant> restaurants = generateRestaurants();
    auto getPayload = [](const Restaurant& r)  {return r;};
    auto getPosition = [](const Restaurant& r) {return r.location;};
    NearestNeighbors::Structure<Restaurant> restaurantLookup(restaurants.begin(),
                                                             restaurants.end(),
                                                             getPosition,
                                                             getPayload);
    std::vector<Real> myposition = getMyPosition();
    /// I want to go to the nearest restaurant.
    Restaurant nearest = restaurantLookup.findFirstExactNearest(myposition);
    std::cout << "I am going to " << nearest.name << std::endl;
    return 0;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Could you add an example how to use this in a useful way? I do not see the problem your code solves. It is not immediately obvious why I want to use your Queue instead of an std::queue or an std::vector, what Structure is for and why you don't just have a free function to find nearest neighbors in a more general way. \$\endgroup\$ – nwp Oct 26 '14 at 13:10
  • \$\begingroup\$ I would like to see some reasoning. E.g. why Queue and not std::queue or std::priority_queue. Why Batch and not two iterators (It from, It to). \$\endgroup\$ – firda Oct 26 '14 at 17:10
  • \$\begingroup\$ @nwp I am sorry for the confusion. I edited my question to answer your questions as much as I could. The purpose of metric structures is to find nearest neighbors in logarithmic, instead of linear time. For this purpose, the data needs to be in a tree-like data structure, hence the use of a class and not just free functions. Since there are many approaches how to implement this metric data structure (K-d trees, M-trees, ...) I want to make a unified interface, which would capture the nearest-neighbor-y essence of these data structures. \$\endgroup\$ – Martin Drozdik Oct 26 '14 at 23:42
  • \$\begingroup\$ @firda I edited my question to provide reasoning for Queue. As far as Batch is concerned, it is supposed to store all the payload associated to one node. Why did I use Batch instead of a pair of iterators? That is a good question. It just never came to my mind. What is the advantage of returning a pair of iterators? \$\endgroup\$ – Martin Drozdik Oct 26 '14 at 23:44
  • \$\begingroup\$ @MartinDrozdik: I was a bit confused what Batch really is... attributes e.g. like distance, travel speed, ...? Two iterators are usually used as arguments to e.g. remove-range. \$\endgroup\$ – firda Oct 27 '14 at 7:20
1
\$\begingroup\$

First scan

using Real = double - not bad, but I would use another template parameter (defaulted to double).

Queue - now we know it is actually std::priority_queue (which is heap).

  • Why removing from highest (not least) distance?
  • Why Pair from pop, but Real from peek?
  • Why heap at all? It could be constructed as a heap, but it is rather used as a set/vector/deque once it is returned. Maybe Matches would be better name for it (you should describe the purpose, not the internal structure), but I am no expert to know what is the real purpose and what algorithms can be used.

TPayload vs. Batch - the later seems to allow multiple nodes (e.g. cities or what payload can be) in same place + accept/return list of such nodes/elements. What I am really missing is some Doxygen documentation describing every method and adding some usage example (note: the example was edited in the question while I was writing this review).

void insert (const TVector& position, const Batch& toInsert); - I would personally add another method taking pair of iterators:

template<class It> void insert(const TVector& position, It from, It to) {
    static_assert(std::is_same<TPayload,std::iterator_traits<It>::value_type>::value, ...);

std::size_t computeSize() const; - what is that method doing? Number of vectors? Something different?

The names and design

The Structure looks like std::(multi)map, where TVector is something like location/position (seen in example) - a key - and TPayload is the value. Why not naming it that way? As already mentioned, TVector may describe what is it about, but still is too connected with the implementation, not the purpose. (The location could be enumeration and our metric could measure the distance using dijkstra or whatever algorithm.)

findFirstExactNearest vs. findExactNearest + Batch: I would take inspiration in std::equal_range and use pair of iterators - there would be no need for Batch and the two methods could be made one.

ExactNearest vs. ApproximateNearest: which of the two will be most used? What about adding another template parameter (bool or enum (class)) for it? The name could then be simply nearest (find can be removed as well).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.