Grupowanie obiektów według zbioru atrybutów

Nigdy dotąd nie zagłębiałem się w tematy związane ze statystyką, Big Data itp. Zapewne ktoś już ten problem naukowo rozwiązał, więc nie chciałbym wynajdywać koła nowo.

Zagadnienie wygląda następująco:

Mam zbiór obiektów, które są opisane atrybutami. Każdy obiekt ma Id, powiedzmy że int32. Dla uproszczenia każdy atrybut też ma swoje Id w postaci int32. Obiekt może być opisany różnym zbiorem atrybutów. Przykładowo Obiekt1 jest opisany atrybutami (1, 2, 3), Obiekt2 (4, 5), Obiekt3 (2, 4, 3).

Z jakich struktur danych/algorytmów skorzystać, aby móc pogrupować obiekty według posiadanych atrybutów? Chodzi o to, że w następstwie pogrupowania, chciałbym mieć możliwość podania listy atrybutów do teoretycznej funkcji search(), tak aby uzyskać zbiór Id obiektów opisanych tymi atrybutami. Rozwiązania probabilistyczne dające przedziały lub false positive również są akceptowalne.

Natknąłem się na https://en.wikipedia.org/wiki/Hypergraph, które w teorii mogłyby się przydać do ręcznej implementacji rozwiązania. Mile widziany były jednak wskazówki, z jakich istniejących bibliotek, struktur, algorytmów warto skorzystać, by rozwiązać taki problem. :)

Ilość atrybutów jest z góry znana i wystąpi z każdym obiektem - czy nieznana, płynna, dodawana dynamicznie po czasie, i będzie lużno wiązana ?
To poprowadzi projekt w zupełnie inne strony

Ile obiektów? 100, 50 tys, milion, miliard?
Ile atrybutów (u początku projektu / ew po spuchnieci, zaleznie od odp. powyżej) 10 czy 1000 ?

A to nie jest jakies trywialne? W ktorym miejscu jest problem? W zlozonosci obliczeniowej? Za slabo to opisales.

Problem wydaje się być związany z brakiem koncepcji ;) Czy czajnik powinien być grupowany z oponą?

@ZrobieDobrze: Liczba atrybutów będzie stała dla obiektu, górna granica to około 100 atrybutów. Obiektów w tej chwili jest poniżej 100k, będą przyrastać.
@stivens i @yarel: Być może problem jest trywialny, w sumie wynika z braku koncepcji. Dlatego jej poszukuję, bo dotychczas nie zajmowałem się takimi problemami :)

No to search o zlozonosci O(n) bedzie ok dla Ciebie?

Kodujesz zbior atrybutow jako dwie maski binarne (zakladam tutaj maske binarna jako liczbe 64bitowa). Bo masz max 100 atrybutow. (Jesli dobrze zrozumialem)

Potem jak szukasz to input do search tez zamieniasz w maski bitowe i po kolei robisz bitowy AND. (Taki filter)

Jesli id atrybutu nie moze byc z przedzialu 1-100 (bo jeden obiekt ma maks 100 atrybutow ale samych atrybutow jest 2^32) to wtedy zamiast masek bitowych dajesz zbiory. I liniowo porownujesz zbiory z inputem. Kwestia tylko jak szybko to ma dzialac. A tego nie okresliles.

Może w chomiku? Ten przykład, który podałeś znajduje obiekty 1 i 3.

#!/usr/local/bin/chomik

type 
    search_argument_range=1..5; # we may have max 5 arguments in our query
expand(1);

variable object (X:integer) has attribute (Y:integer):boolean;

let object (X:integer) has attribute (Y:integer)=value boolean false;

# data:
let object 1 has attribute 1=value boolean true;
let object 1 has attribute 2=value boolean true;
let object 1 has attribute 3=value boolean true;

let object 2 has attribute 4=value boolean true;
let object 2 has attribute 5=value boolean true;

let object 3 has attribute 2=value boolean true;
let object 3 has attribute 4=value boolean true;
let object 3 has attribute 3=value boolean true;

let max object id = value integer 10;

# search

variable search argument active (NUMBER:search_argument_range):boolean, search argument (NUMBER:search_argument_range):integer;
let search argument active (NUMBER:search_argument_range)=value boolean false;

variable search response (X:integer):boolean;
let search response (X:integer)=value boolean false;


variable stop search on (A:compare_result):code;
let stop search on lower=value code {};
let stop search on greater=value code {};
let stop search on equal=value code { let the break flag = value boolean true; };

variable current object id:integer;
variable match the search argument (Q:boolean):code;
let match the search argument true=value code {};
let match the search argument false=value code { let search response <current object id>=value boolean false; };

variable match result:boolean;
let match result=value boolean false;


variable on search argument (B:boolean) do processing:code;
let on search argument false do processing = value code {};
let on search argument true do processing = value code 
{
    let match result=<object <current object id> has attribute <search argument <current argument number>>>;
    <match the search argument <match result>>;
};


variable on current object and current search attribute (X:search_argument_range) do processing:code;
let on current object and current search attribute (X:search_argument_range) do processing = value code
{
    let variable current argument number=value integer [(X:search_argument_range)];
    <on search argument <search argument active <current argument number>> do processing>;
};



variable for all objects (X:integer) do search:code;
let for all objects (X:integer) do search=value code
{
    let current object id = value integer [(X:integer)];
    let search response (X:integer)=value boolean true;
    
    <on current object and current search attribute (S:search_argument_range) do processing>;    

    <compare "integer" (X:integer) <max object id>>;
    <stop search on <the compare result>>;
};

variable search:code;
let search =value code
{
    <for all objects (A:integer) do search>;
    let the break flag = value boolean false;
};

variable on (B:boolean) print current object id:code;
let on false print current object id=value code {};
let on true print current object id=value code { <print "object" <current object id>>; };



# printing out the response
variable for all objects (P:integer) do print:code;

let for all objects (P:integer) do print =value code
{
    let current object id = value integer [(P:integer)];

    <on <search response <current object id>> print current object id>;
    
    <compare "integer" (P:integer) <max object id>>;
    <stop search on <the compare result>>;
};

variable search response print:code;
let search response print=value code
{
    <for all objects (Y:integer) do print>;
    let the break flag=value boolean false;
};

# usage example:
#
# .. looking for objects with the attribute 2 and 3
#
let search argument active (NUMBER:search_argument_range)=value boolean false;
let search argument 1=value integer 2;
let search argument active 1=value boolean true;
let search argument 2=value integer 3;
let search argument active 2=value boolean true;
let b=value boolean false;

<search>;

<search response print>;