海量数据的“交并集”操作,该怎么解决

海量数据的“交并集”操作
应用场景大致是这样：
有上亿条数据，每条数据属于若干个类别（大约属于3到10个类别），
总共约有近千个不同的类别，每个类别含有的数据量从几千到上亿不等。

现在需要迅速的查询出某几个类别，经过交、并操作后的数据量。


现在的处理方式是：
对原始的上亿条数据，随机抽样出千分之一的数据量；
对这抽样的数据，分别赋上从1开始的序号；
然后，对这抽样的数据中的每个类别分别建立一个bitmap，
bitmap的每个下标，对应着某一条抽样数据，
若置一，则表示该类别含有该下标所对应的数据。

当有交并集查询到来时，取出相应类别的bitmap，进行交并操作，
并得到结果bitmap的置一数量，然后再除以抽样率，得到近似的原始数据的交并集的数据量。


现在，希望能够尽可能精确的得到原始数据的交并集数据量，
请问大家有没有什么更好的方案啊？
比如说，是否可以建立多级的bitmap，或者分段的bitmap等（自己瞎捉摸着）。

望大家不吝赐教，
来者有分啊！

[解决办法]
观望！！！！！！ 这么大的数据量暂时没处理过。。。。。
[解决办法]
这个数据量是什么？只是count么？
[解决办法]
求交集用小集合做HASH，求并集用bitmap，复杂度不可能低于O(n)吧
[解决办法]
不知redis数据库是否可以用上，天然的对集合操作的支持，而且性能很好。
[解决办法]
每条数据属于若干个类别, 用一个int字段("Type")来表示这个
如果只属于第一个类别用 1, 
第2个类别 2
同时属于两个类别 3

最后数据按这个 Type做索引, 以后的检索就很快了



[解决办法]

探讨

现在需要迅速的查询出某几个类别，经过交、并操作后的数据量。

[解决办法]
文章 和 标签？

关系数据库 采用 分区表，应该能解决
[解决办法]
有统计数据吗？(2-10)个类别的数据比重大概是多少？其实我想知道是不是绝大部分的数据只有2~3个类别？
[解决办法]
估计没什么好办法，你看google的查询结果数量都不给准确值，结果数量过多的时候连综合权值的计算的抛弃了，归并的开销太大。
[解决办法]
有一个不怎么好的想法(仅仅是个常数级的处理)，将分类数据按照数量排序形成C个等级，然后将每个分类数据按照最小关联等级分成C分，归并的时候就只需要处理有关联的等级数据。
[解决办法]
看贴总是不回 ，一直没提升等级和增加经验，现在我明白了，反正回贴可以升级 ，也可以赚经验，而升级又需要经验 ，我就把这句话复制下来，遇贴就灌水，捞经验就闪


[解决办法]

C/C++ code

//输出PROG中有但LIST中没有的文本行，即集合PROG-LIST#include <stdio.h>#include <string.h>#include <stdlib.h>#include <search.h>#define MAXLINES 1000000#define MAXCHARS 256char buf[MAXLINES][MAXCHARS];char P[256]="PROG";//程序Program需要的文件列表char L[256]="LIST";//dir /b /s生成的实际文件列表ListFILE *fp,*fl;int c,n,L1,hh;int ignore_case=0;char ln[MAXCHARS];int icompare(const void *arg1,const void *arg2) {   return stricmp((char *)arg1,(char *)arg2);}int compare(const void *arg1,const void *arg2) {   return strcmp((char *)arg1,(char *)arg2);}int main(int argc,char **argv) {    if (argc>1) strcpy(P,argv[1]);//命令行参数1覆盖PROG    if (argc>2) strcpy(L,argv[2]);//命令行参数2覆盖LIST    if (argc>3) ignore_case=1;//若存在命令行参数3，忽略大小写    if ((fl=fopen(L,"rt"))==NULL) {        fprintf(stderr,"Can not open %s\n",L);        fprintf(stderr,"Usage: %s [PROG] [LIST] [-i]\n",argv[0]);        return 1;    }    if ((fp=fopen(P,"rt"))==NULL) {        fclose(fl);        fprintf(stderr,"Can not open %s\n",P);        return 2;    }    n=0;    hh=0;    while (1) {        if (fgets(ln,MAXCHARS,fl)==NULL) break;//        hh++;        L1=strlen(ln)-1;        if ('\n'!=ln[L1]) {//超长行忽略后面内容            fprintf(stderr,"%s Line %d too long(>%d),spilth ignored.\n",L,hh,MAXCHARS);            while (1) {                c=fgetc(fl);                if ('\n'==c || EOF==c) break;//            }        }        while (1) {//去掉行尾的'\n'和空格            if ('\n'==ln[L1] || ' '==ln[L1]) {                ln[L1]=0;                L1--;                if (L1<0) break;//            } else break;//        }        if (L1>=0) {            strcpy(buf[n],ln);            n++;            if (n>=MAXLINES) {                fclose(fl);                fclose(fp);                fprintf(stderr,"%s up to %d lines",L,MAXLINES);                return 3;            }        }    }    fclose(fl);    if (ignore_case) qsort(buf,n,MAXCHARS,icompare);    else qsort(buf,n,MAXCHARS,compare);    hh=0;    while (1) {        if (fgets(ln,MAXCHARS,fp)==NULL) break;//        hh++;        L1=strlen(ln)-1;        if ('\n'!=ln[L1]) {//超长行忽略后面内容            fprintf(stderr,"%s Line %d too long(>%d),spilth ignored.\n",P,hh,MAXCHARS);            while (1) {                c=fgetc(fp);                if ('\n'==c || EOF==c) break;//            }        }        while (1) {//去掉行尾的'\n'和空格            if ('\n'==ln[L1] || ' '==ln[L1]) {                ln[L1]=0;                L1--;                if (L1<0) break;//            } else break;//        }        if (L1>=0) {            if (ignore_case) {                if (NULL==bsearch(ln,buf,n,MAXCHARS,icompare)) printf("%s\n",ln);            } else {                if (NULL==bsearch(ln,buf,n,MAXCHARS,compare)) printf("%s\n",ln);            }        }    }    fclose(fp);    return 0;} 
 
[解决办法]
C/C++ code
#include <stdio.h>#include <stdlib.h>#include <time.h>int d[6];int i,n,a,b,t;int c,j;void main() {    srand(time(NULL));    printf("shuffle 0..n-1 demo\n");    for (n=1;n<=5;n++) {/* 测试1～5个元素 */        printf("_____n=%d_____\n",n);        j=1;        for (c=1;c<=n;c++) j=j*c;/* j为n! */        j*=n*2;        for (c=1;c<=j;c++) {/* 测试n*2*n!次 */            for (i=0;i<n;i++) d[i]=i;/* 填写0～n-1 */            for (i=n;i>0;i--) {/* 打乱0～n-1 */                a=i-1;b=rand()%i;                if (a!=b) {t=d[a];d[a]=d[b];d[b]=t;}            }            printf("%04d:",c);            for (i=0;i<n;i++) printf("%d",d[i]);            printf("\n");        }    }    printf("shuffle 1..n demo\n");    for (n=1;n<=5;n++) {/* 测试1～5个元素 */        printf("_____n=%d_____\n",n);        j=1;        for (c=1;c<=n;c++) j=j*c;/* j为n! */        j*=n*2;        for (c=1;c<=j;c++) {/* 测试n*2*n!次 */            for (i=1;i<=n;i++) d[i]=i;/* 填写1～n */            for (i=n;i>1;i--) {/* 打乱1～n */                a=i;b=rand()%i+1;                if (a!=b) {t=d[a];d[a]=d[b];d[b]=t;}            }            printf("%04d:",c);            for (i=1;i<=n;i++) printf("%d",d[i]);            printf("\n");        }    }}
[解决办法]
哇哦  这么专业 可惜研究方向不同  帮不上什么吖
[解决办法]
没处理过这么大的数据

[解决办法]
探讨


这里的“最小关联等级”指的是什么？

引用:

有一个不怎么好的想法(仅仅是个常数级的处理)，将分类数据按照数量排序形成C个等级，然后将每个分类数据按照最小关联等级分成C分，归并的时候就只需要处理有关联的等级数据。

[解决办法]
探讨

C1:[{C1:[D5]},{C2:[D1,D2,D3]},{C3:[D4]}]
C2:[{C2:[D2,D3,D6]},{C3:[D1]}]
C3:[{C3:[D1,D4,D7]}]

[解决办法]
楼主，不知道你是在什么平台上开发，对于性能要求到底有多高？究竟是内存不够，还是硬盘不够，抑或运算时间不够？

照理来说10亿也不是一个很大的数值呀，10亿位的bitmap内存占用不到60M。

预处理的时候创建1000个种类的bitmap，硬盘占用也就60G。
[解决办法]
文章 和 标签？
[解决办法]
js代码js代码
[解决办法]
看贴总是不回 ，一直没提升等级和增加经验，现在我明白了，反正回贴可以升级 ，也可以赚经验，而升级又需要经验 ，我就把这句话复制下来，遇贴就灌水，捞经验就闪
[解决办法]
只是数量，不需要交并之后的具体元素。
花时间穷举，把所有的可能的交并结果都记下来吧。
假设有10个类，有2^10个可能的交并结果，很小的。

如果需要，可以增量式的更新这个结果，在每次增删改数据的时候。
[解决办法]
不敢说。。什么是海量？定义范围？
[解决办法]
战神的代码是在刷分，以前用过的。。。
[解决办法]
支持39楼。
[解决办法]
1,分段
2,哈希
复杂度做到加法O(A+B)
[解决办法]
同意楼上
[解决办法]
知道啦   谢谢
[解决办法]
做足排序、筛选后再说别的先 
 
[解决办法]
建议楼主不妨参考一下点积拓扑的处理方式~ 

 

查看更多 下一篇